package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.PrintUtils;

import java.util.Arrays;

public class UniqueBinarySearchTrees {

    /**
     * 要求出所有二叉搜索树的种数，根据 {@link UniqueBinarySearchTrees2} 可知，
     * 我们可以依次枚举根节点，然后列出所有左子树的数量和右子树的数量，可见 {@link UniqueBinarySearchTrees#numTrees2}
     * 但是此种方法超时，这时我们可以用动态规划解决问题
     * 假设 n = 3, 根节点root = 1,
     *  此刻左子树没有节点，只有null一种情况，
     *  右节点为(2, 3)，有2为右子树根节点和3为右子树根节点两种情况
     *  f(3) = f(0) * f(2) + f(1) * f(1) + f(2) * f(0)
     * 状态转移方程 f(n) = f(1) * f(n - 1) + ... + f(n - 1) * f(1)
     */
    public int numTrees(int n) {
        if (n <= 2){
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; ++i){
            for (int j = 0; j < i; ++j){
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }

    public int numTrees2(int begin, int end){
        if (begin > end){
            return 1;
        }
        int num = 0;
        for (int i = begin; i <= end; ++i){
            num += numTrees2(begin, i - 1) * numTrees2(i + 1, end);
        }
        return num;
    }

    public static void main(String[] args) {
        int n = 4;
        int res = new UniqueBinarySearchTrees().numTrees(n);
        System.out.println(res);
    }
}
